Euler Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

   3
  7 5
 2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it.


In [1]:
infile = open('data/p067_triangle.txt', 'r')
triangle = []
for line in infile:
    triangle.append(list(map(int, line.split())))

rows = len(triangle)
w = triangle[0]

for k in range(1,rows):
    w2 = [0]*(k+1)
    w2[0] = w[0] + triangle[k][0]
    w2[k] = w[k-1] + triangle[k][k]
    for i in range(1,k):
        w2[i] = max(w[i-1],w[i]) + triangle[k][i]
    w = w2
print(max(w))


7273

In [ ]: